/**
 * @(#)Combination.java       2008-9-17
 *
 */
package edu.pku.ss.mumcut.common;

import java.util.Vector;

/**This class is used to traverse the combination in a set.
 * For example, we want to take 2 number in a set of 4 numbers(for example 0 1 2 )
 * All the combination will be (0 1),(0,2),(1,2)
 * 
 * @author power
 *
 */

public class Combination
{

		
    	/**The amount of the set which is been select from
    	 * For example, we want select 2 in 3 numbers, setNum is 3
    	 *
    	 */
    	private int setNum;
    	
    	/**The number need to select
    	 * For example, we want select 2 in 3 numbers, selectNum is 2
    	 *
    	 */
    	private int selectNum;
    	
    	
    	/**Array used to contain the current selected numbers
    	 * 
    	 *
    	 */
    	private int currentSelected[];
    	
    	
    	/**identify setted or not
    	 * 
    	 *
    	 */
    	private boolean isSetted;
    	
    	
	 	/**
	 	 * @return whether has More Combination or not
	 	 */
	 	public boolean hasMoreCombination()
	    {
	        if(!isSetted)
	            return true;
	        if(selectNum == 0)
	            return false;
	        for(int i = 0; i < currentSelected.length; i++)
	            if((setNum - selectNum) + i != currentSelected[i])
	                return true;

	        return false;
	    }

	 	
	    /**
	     * @param setNBR the number of the set
	     * @param selectNBR the number need to select
	     * @throws Exception 
	     */
	    public Combination(int setNBR, int selectNBR)
	        throws Exception
	    {
	        if(setNBR < selectNBR || setNBR < 1 || selectNBR <= 0)
	        {
	            throw new Exception("wrong argument for struct of Combination");
	        } else
	        {
	            this.setNum = setNBR;
	            this.selectNum = selectNBR;
	            isSetted = false;
	            currentSelected = new int[selectNBR];
	        }
	    }

	    private int getTheLastCanAddIndex()
	    {
	        for(int i = selectNum - 1; i >= 0; i--)
	            if(currentSelected[i] < (setNum - selectNum) + i)
	                return i;

	        return -1;
	    }

	    
	    /**If hasMoreCombination,can get the NextCombination
	     * @return
	     * @throws Exception
	     */
	    public Vector<Integer> getNextItem()
	        throws Exception
	    {
	        if(isSetted)
	        {
	            int j = getTheLastCanAddIndex();
	            if(j != -1)
	            {
	                currentSelected[j]++;
	                for(int k = j + 1; k < selectNum; k++)
	                    currentSelected[k] = (currentSelected[j] + k) - j;

	                return wrap(currentSelected);
	            } else
	            {
	                throw new Exception("can't add more");
	            }
	        }
	        for(int i = 0; i < selectNum; i++)
	            currentSelected[i] = i;

	        isSetted = true;
	        return wrap(currentSelected);
	    }

	    
	    /**Wrap the status of the current selections
	     * @param status
	     * @return
	     */
	    private Vector<Integer> wrap(int status[])
	    {
	        Vector<Integer> rs = new Vector<Integer>();
	        for(int i = 0; i < status.length; i++)
	            rs.add(new Integer(status[i]));

	        return rs;
	    }

}